#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5005;

struct Node{
    int t;
    LL w;
    Node(){}
    Node(int t_,LL w_):t{t_},w{w_}{}
};
int n,m;
queue<int> que;
LL minDis[N];
int cnt[N];
bool inque[N];
vector<Node> edges[N];


int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int s,t;
        LL e;
        scanf("%d%d%lld",&s,&t,&e);
        edges[s].emplace_back(Node(t,e));
    }

    for(int i=1;i<=n;i++){
        que.push(i);
        inque[i] = true;
        cnt[i] = 1;
        minDis[i] = 1e9+1;
    }
    minDis[1] = 0;

    while(!que.empty()){
        int x = que.front(); que.pop();
        inque[x] = false;
        for(auto node:edges[x]){
            int y = node.t;
            LL dis2 = minDis[x] + node.w;
            if(dis2<minDis[y]){
                minDis[y] = dis2;
                if(!inque[y]){
                    que.push(y);
                    inque[y] = true;
                    cnt[y]++;
                    if(cnt[y]>n){
                        printf("NO");
                        return 0;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%lld ",-minDis[i]);
    }
    return 0;
}